#include <stdio.h> 
#include <stdlib.h> 
 
struct Node { 
    int data; 
    struct Node* left; 
    struct Node* right; 
}; 
 
struct Node* newNode(int value) { 
    struct Node* node = (struct Node*)malloc(sizeof(struct Node)); 
    node->data = value; 
    node->left = node->right = NULL; 
    return node; 
} 
 
struct Node* insert(struct Node* node, int value) { 
    if (node == NULL) return newNode(value); 
    if (value < node->data) 
        node->left = insert(node->left, value); 
    else if (value > node->data) 
        node->right = insert(node->right, value); 
    return node; 
} 
 
void inOrder(struct Node* root) { 
    if (root != NULL) { 
        inOrder(root->left); 
        printf("%d ", root->data); 
        inOrder(root->right); 
    } 
} 
 
struct Node* search(struct Node* root, int value) { 
    if (root == NULL || root->data == value) 
        return root; 
    if (value < root->data) 
        return search(root->left, value); 
    return search(root->right, value); 
} 
 
struct Node* minValueNode(struct Node* node) { 
    struct Node* current = node; 
    while (current && current->left != NULL) 
        current = current->left; 
    return current; 
} 
 
struct Node* deleteNode(struct Node* root, int value) { 
    if (root == NULL) return root; 
    if (value < root->data) 
        root->left = deleteNode(root->left, value); 
  
    else if (value > root->data) 
        root->right = deleteNode(root->right, value); 
    else { 
        if (root->left == NULL) { 
            struct Node* temp = root->right; 
            free(root); 
            return temp; 
        } else if (root->right == NULL) { 
            struct Node* temp = root->left; 
            free(root); 
            return temp; 
        } 
        struct Node* temp = minValueNode(root->right); 
        root->data = temp->data; 
        root->right = deleteNode(root->right, temp->data); 
    } 
    return root; 
} 
 
int main() { 
    struct Node* root = NULL; 
    int choice, value; 
     
    while (1) { 
        printf("\nBinary Search Tree Operations Menu:\n"); 
        printf("1. Insert\n"); 
        printf("2. Search\n"); 
        printf("3. Delete\n"); 
        printf("4. Display (In-order Traversal)\n"); 
        printf("5. Exit\n"); 
        printf("Enter your choice: "); 
        scanf("%d", &choice); 
         
        switch (choice) { 
            case 1: 
                printf("Enter value to insert: "); 
                scanf("%d", &value); 
                root = insert(root, value); 
                break; 
 
            case 2: { 
                printf("Enter value to search: "); 
                scanf("%d", &value); 
                struct Node* found = search(root, value); 
                if (found != NULL) 
                    printf("Value %d found in the BST.\n", value); 
                else 
                    printf("Value %d not found in the BST.\n"); 
                break; 
            } 
 
            case 3: 
                printf("Enter value to delete: "); 
                scanf("%d", &value); 
                root = deleteNode(root, value); 
  
                break; 
 
            case 4: 
                printf("In-order traversal of the BST: "); 
                inOrder(root); 
                printf("\n"); 
                break; 
 
            case 5: 
                exit(0); 
 
            default: 
                printf("Invalid choice! Please choose again.\n"); 
        } 
    } 
 
    return 0; 
}